Information Source Detection in the SIR Model: A Sample Path Based Approach

摘要

This paper studies the problem of detecting the information source in anetwork in which the spread of information follows the popularSusceptible-Infected-Recovered (SIR) model. We assume all nodes in the networkare in the susceptible state initially except the information source which isin the infected state. Susceptible nodes may then be infected by infectednodes, and infected nodes may recover and will not be infected again afterrecovery. Given a snapshot of the network, from which we know all infectednodes but cannot distinguish susceptible nodes and recovered nodes, the problemis to find the information source based on the snapshot and the networktopology. We develop a sample path based approach where the estimator of theinformation source is chosen to be the root node associated with the samplepath that most likely leads to the observed snapshot. We prove forinfinite-trees, the estimator is a node that minimizes the maximum distance tothe infected nodes. A reverse-infection algorithm is proposed to find such anestimator in general graphs. We prove that for $g$-regular trees such that$gq>1,$ where $g$ is the node degree and $q$ is the infection probability, theestimator is within a constant distance from the actual source with a highprobability, independent of the number of infected nodes and the time thesnapshot is taken. Our simulation results show that for tree networks, theestimator produced by the reverse-infection algorithm is closer to the actualsource than the one identified by the closeness centrality heuristic. We thenfurther evaluate the performance of the reverse infection algorithm on severalreal world networks.